Model Counting of Query Expressions: Limitations of Propositional Methods

摘要

Query evaluation in tuple-independent probabilistic databases is the problemof computing the probability of an answer to a query given independentprobabilities of the individual tuples in a database instance. There are twomain approaches to this problem: (1) in `grounded inference' one first obtainsthe lineage for the query and database instance as a Boolean formula, thenperforms weighted model counting on the lineage (i.e., computes the probabilityof the lineage given probabilities of its independent Boolean variables); (2)in methods known as `lifted inference' or `extensional query evaluation', oneexploits the high-level structure of the query as a first-order formula.Although it is widely believed that lifted inference is strictly more powerfulthan grounded inference on the lineage alone, no formal separation haspreviously been shown for query evaluation. In this paper we show such a formalseparation for the first time. We exhibit a class of queries for which model counting can be done inpolynomial time using extensional query evaluation, whereas the algorithms usedin state-of-the-art exact model counters on their lineages provably requireexponential time. Our lower bounds on the running times of these exact modelcounters follow from new exponential size lower bounds on the kinds of d-DNNFrepresentations of the lineages that these model counters (either explicitly orimplicitly) produce. Though some of these queries have been studied before, nonon-trivial lower bounds on the sizes of these representations for thesequeries were previously known.